import java.util.*;

public class Test {
    //题目1：不同的二叉搜索树 II
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> list = new LinkedList<>();
        if(start > end){
            list.add(null);
            return list;
        }
        for(int i = start; i <= end; i++){
            List<TreeNode> leftNodes = generateTrees(start, i - 1);
            List<TreeNode> rightNodes = generateTrees(i + 1, end);
            for(TreeNode left : leftNodes){
                for(TreeNode right : rightNodes){
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    list.add(node);
                }
            }
        }
        return list;
    }

    // 题目2：路径总和 III
    public int pathSum(TreeNode root, int target) {
        if(root == null){
            return 0;
        }
        int ret = rootPath(root, target);
        ret += pathSum(root.left, target);
        ret += pathSum(root.right, target);
        return ret;
    }
    public int rootPath(TreeNode root, long target){
        int ret = 0;
        if(root == null){
            return 0;
        }
        int val = root.val;
        if(target == val){
            ret++;
        }
        long tar = target - root.val;
        ret += rootPath(root.left, tar);
        ret += rootPath(root.right, tar);
        return ret;
    }

    // 题目3：求根节点到叶节点数字之和
    // 方法一：
    Deque<Integer> queue = new LinkedList<>();
    int ret;
    public int sumNumbers(TreeNode root) {
        dsf(root);
        return ret;
    }

    public void dsf(TreeNode root){
        if(root == null){
            return;
        }
        queue.offer(root.val);
        if(root.left == null && root.right == null){
            StringBuilder s = new StringBuilder();
            for(Integer x : queue){
                s.append(x+"");
            }
            ret += Integer.parseInt(s.toString());
        }
        dsf(root.left);
        dsf(root.right);
        queue.pollLast();
    }

    // 方法二
    public int sumNumbers1(TreeNode root) {
        return pathSum1(root, 0);
    }

    public int pathSum1(TreeNode root, int sum){
        if(root == null){
            return 0;
        }
        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null){
            return sum;
        }else{
            return pathSum1(root.left, sum) + pathSum1(root.right, sum);
        }
    }

    // 题目4： 二叉树的直径
    int max ;
    public int diameterOfBinaryTree(TreeNode root) {
        sideNum(root);
        return max;
    }

    public int sideNum(TreeNode root){
        if(root == null ){
            return 0;
        }
        int left =  sideNum(root.left); // 左边以串联的方式连成的最长的一串
        int right = sideNum(root.right); // 右边以串联的方式连成的最长的一串
        max = Math.max(max,  left + right);
        return Math.max(left, right) + 1; // 一个节点有一条边
    }

    // 题目5： 二叉树中的最大路径和
    int max1 = -1001;
    public int maxPathSum(TreeNode root) {
        path(root);
        return max1;
    }

    public int path(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = path(root.left);
        int right = path(root.right);
        int maxVal = root.val;
        if(left > 0) maxVal += left;
        if(right > 0) maxVal += right;
        max1 = Math.max(max1, maxVal);
        int ret = Math.max(left, right);
        return  ret > 0 ? ret + root.val : root.val;
    }

    // 代码更简练一点：
    public int maxPathSum1(TreeNode root) {
        path1(root);
        return max1;
    }
    public int path1(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = Math.max(path(root.left), 0);
        int right = Math.max(path(root.right), 0);
        max1 = Math.max(max1, left + right + root.val);
        return  Math.max(left, right) + root.val;
    }

}
